package JZ_Offer.algorithm.dp;

/**
 * 连续子数组的最大和
 * 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *
 * 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。
 * 但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？
 * 例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
 * 给一个数组，返回它的最大连续子序列的和 (子向量的长度至少是1)
 *
 * @Author piper
 * @Date 2019/12/30 11:25 上午
 */
public class JZ42_连续子数组的最大和 {
    private static int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0]; //保存最大和
        int sum = array[0]; //每次循环的数据和
        for (int i = 1; i < array.length; i++) {
            int cur = sum + array[i];
            // 判断 当前元素作为子序列的和还是作为新的子序列第一个元素
            // 可以想象两个子序列：1前一个子序列到当前元素 2当前元素自己组成的子序列
            // 当子序列加上当前元素后 的和 小于当前元素
            // 也就是子序列 1<2 那么就要重置子序列为2了
            sum = cur < array[i] ? array[i] : cur;
            max = max < sum ? sum : max; //比较得出最大值
        }
        return max;
    }


    public static void main(String[] args) {
        System.out.println(FindGreatestSumOfSubArray(new int[]{6, -3, -2, 7, -15, 1, 2, 2}));
        System.out.println(FindGreatestSumOfSubArray(new int[]{1, -2, 3, 10, -4, 7, 2, -5}));
        System.out.println(FindGreatestSumOfSubArray(new int[]{-2, -8, -1, -5, -9}));
    }
}
